package cn.xaut.动态规划;

/**
 * 53. 最大子序和
 */
public class demo53 {

    // 暴力解法——超时
    public int maxSubArray(int[] nums) {

        int len = nums.length;
        if (len == 1)
            return nums[0];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += nums[k];
                }
                res = Math.max(res, sum);
            }
        }
        return res;
    }

    // 贪心算法
    public int maxSubArray2(int[] nums) {

        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;

            res = Math.max(res, sum);
        }
        return res;
    }

    public static void main(String[] args) {

        System.out.println(new demo53().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4})); // 6
        System.out.println(new demo53().maxSubArray(new int[]{1})); // 1
        System.out.println(new demo53().maxSubArray(new int[]{0})); // 0
        System.out.println(new demo53().maxSubArray(new int[]{-1})); // -1
        System.out.println(new demo53().maxSubArray(new int[]{-100000})); // -100000
    }
}
